package com.practice.niuke.new_direct_practice.class06;

import java.util.HashMap;

/**
 * 已知一棵二叉树中没有重复节点， 并且给定了这棵树的中序遍历数组和先序遍历 数组，
 * 返回后序遍历数组。
 * 比如给定:
 * int[] pre = { 1, 2, 4, 5, 3, 6, 7 };
 * int[] in = { 4, 2, 5, 1, 6, 3, 7 }; 返回:
 * {4,5,2,6,7,3,1}
 */
public class Code04_PreAndInArrayToPosArray {

	/**
	 * 调用递归函数的主函数
	 *
	 * @param pre 先序数组
	 * @param in 中序数组
	 * @return int[]
	 */
	public static int[] getPostArray(int[] pre, int[] in) {
		if (pre == null || in == null) {
			return null;
		}
		if (pre.length != in.length){
		    return null;
        }
		int N = pre.length;
		int[] pos = new int[N];
		set(pre, in, pos,
                0, N - 1,
                0, N - 1,
                0, N - 1);
		return pos;
	}

	/**
	 * 递归函数，
	 * 利用pre[L1......R1]以及in[L2.......R2] ==> pos[L3......R3]
     * L1...R1 和 L2...R2 和 L3...R3 一定要等量
	 *
	 * @param pre 先序数组
	 * @param in 中序数组
	 * @param pos 后序数组
	 * @param L1 L1 先序数组的起始位置
	 * @param R1 R1 先序数组的终止位置
	 * @param L2 L2
	 * @param R2 R2
	 * @param L3 L3
	 * @param R3 R3
	 */
	public static void set(int[] pre, int[] in, int[] pos, int L1, int R1, int L2, int R2, int L3, int R3) {
		if (L1 > R1) {// L1 > R1 无效
			return;
		}
		if (L1 == R1) { // 只剩下一个数了，直接填
			pos[L3] = pre[L1];
		}
		// pre = ..[x......]..
        // in  = ..[...x...]..
        // pos = ..[......x]..
		// pos[R3] = pre[L1]，利用先序遍历的最后一个位置，填好后序遍历的第一个位置
		pos[R3] = pre[L1];
		// 在 in 数组中找到根节点(x)的位置
		int find = L2;
		for (; find <= R2; find++) {
			if (in[find] == pre[L1]) {// in[find]==pre[L1]
				break;
			}
		}
		// 左树递归
		// pre L1+1,   L1+find-L2
		// in  L2,     find-1
		// pos L3,     L3+find-L2-1
		set(pre, in, pos,
                L1 + 1, L1 + find - L2,
                L2, find - 1,
                L3, L3 + find - L2 - 1);
		// 右树递归
		// pre L1+find-L2+1,    R1
		// in  find+1,          R2
		// pos L3+find-L2,      R3-1
		set(pre, in, pos,
				L1 + find - L2 + 1, R1,
				find + 1, R2,
				L3 + find - L2, R3 - 1);
	}

	// 没有重复值
	public static int[] getPosArray(int[] pre, int[] in) {
		if (pre == null || in == null) {
			return null;
		}
		int len = pre.length;
		int[] pos = new int[len];
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < len; i++) {
			map.put(in[i], i);
		}
		setPos(pre, 0, len - 1, in, 0, len - 1, pos, len - 1, map);
		return pos;
	}

    /**
     * 傻缓存的方式找中序遍历数组中根节点（x）的位置，进行求解
     *
     * @param pre
     * @param pi
     * @param pj
     * @param in
     * @param ni
     * @param nj
     * @param s
     * @param si
     * @param map
     * @return
     */
	// 返回值
	// 整棵树依次填写在后续数组s中，从右往左
	// 整棵树都填完之后，后续应该填的位置，作为返回值，返回
	public static int setPos(int[] pre, int pi, int pj, int[] in, int ni, int nj, int[] s, int si,
			HashMap<Integer, Integer> map) {
		if (pi > pj) { // 无效范围时，什么也不做
			return si;
		}
		s[si--] = pre[pi];
		int i = map.get(pre[pi]); // 头节点在中序序列中的位置
		// 中序中，找到了头这个值，所在何处，所以，知道，右树，左树分别是多大
		// pre[pj - nj + i + 1 .. pj] 对应上 in[i + 1, nj]
		// 是右树的，先序和中序的结果
		// si
		si = setPos(pre, pj - nj + i + 1, pj, in, i + 1, nj, s, si, map);
		return setPos(pre, pi + 1, pi + i - ni, in, ni, i - 1, s, si, map);
	}

	public static void printArray(int[] arr) {
		if (arr == null) {
			return;
		}
		for (int i = 0; i != arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int[] pre = { 1, 2, 4, 5, 3, 6, 7 };
		int[] in = { 4, 2, 5, 1, 6, 3, 7 };
		int[] pos1 = getPosArray(pre, in);
		int[] pos2 = getPostArray(pre, in);
		printArray(pos1);
		printArray(pos2);

	}
}
